Integral probability metric

From HandWiki
Short description: Class of distance functions defined between probability distributions

In probability theory, integral probability metrics are types of distance functions between probability distributions, defined by how well a class of functions can distinguish the two distributions. Many important statistical distances are integral probability metrics, including the Wasserstein-1 distance and the total variation distance. In addition to theoretical importance, integral probability metrics are widely used in areas of statistics and machine learning.

The name "integral probability metric" was given by German statistician Alfred Müller;[1] the distances had also previously been called "metrics with a ζ-structure."[2]

Definition

Integral probability metrics (IPMs) are distances on the space of distributions over a set [math]\displaystyle{ \mathcal X }[/math], defined by a class [math]\displaystyle{ \mathcal{F} }[/math] of real-valued functions on [math]\displaystyle{ \mathcal{X} }[/math] as [math]\displaystyle{ D_{\mathcal{F}}(P, Q) = \sup_{f \in \mathcal F} \big| \mathbb E_{X \sim P} f(X) - \mathbb E_{Y \sim Q} f(Y) \big| = \sup_{f \in \mathcal F} \big| P f - Q f \big|; }[/math] here the notation P f refers to the expectation of f under the distribution P. The absolute value in the definition is unnecessary, and often omitted, for the usual case where for every [math]\displaystyle{ f \in \mathcal F }[/math] its negation [math]\displaystyle{ -f }[/math] is also in [math]\displaystyle{ \mathcal F }[/math].

The functions f being optimized over are sometimes called "critic" functions;[3] if a particular [math]\displaystyle{ f^* \in \mathcal F }[/math] achieves the supremum, it is often termed a "witness function"[4] (it "witnesses" the difference in the distributions). These functions try to have large values for samples from P and small (likely negative) values for samples from Q; this can be thought of as a weaker version of classifers, and indeed IPMs can be interpreted as the optimal risk of a particular classifier.[5]

The choice of [math]\displaystyle{ \mathcal F }[/math] determines the particular distance; more than one [math]\displaystyle{ \mathcal F }[/math] can generate the same distance.[1]

For any choice of [math]\displaystyle{ \mathcal F }[/math], [math]\displaystyle{ D_{\mathcal F} }[/math] satisfies all the definitions of a metric except that we may have we may have [math]\displaystyle{ D_{\mathcal F}(P, Q) = 0 }[/math] for some P ≠ Q; this is variously termed a "pseudometric" or a "semimetric" depending on the community. For instance, using the class [math]\displaystyle{ \mathcal F = \{ x \mapsto 0 \} }[/math] which only contains the zero function, [math]\displaystyle{ D_{\mathcal F}(P, Q) }[/math] is identically zero. [math]\displaystyle{ D_{\mathcal F} }[/math] is a metric if and only if [math]\displaystyle{ \mathcal F }[/math] separates points on the space of probability distributions, i.e. for any P ≠ Q there is some [math]\displaystyle{ f \in \mathcal F }[/math] such that [math]\displaystyle{ P f \ne Q f }[/math];[1] most, but not all, common particular cases satisfy this property.

Examples

All of these examples are metrics except when noted otherwise.

  • The Wasserstein-1 distance (also called earth mover's distance), via its dual representation, has [math]\displaystyle{ \mathcal F }[/math] the set of 1-Lipschitz functions.
  • The related Dudley metric is generated by the set of bounded 1-Lipschitz functions.
  • The total variation distance can be generated by [math]\displaystyle{ \mathcal F = \{ f : \mathcal X \to \{0, 1\} \} }[/math], so that [math]\displaystyle{ \mathcal F }[/math] is a set of indicator functions for any event, or by the larger class [math]\displaystyle{ \mathcal F = \{ f : \mathcal X \to [0, 1] \} }[/math].
  • The closely related Radon metric is generated by continuous functions bounded in [-1, 1].
  • The Kolmogorov metric used in the Kolmogorov-Smirnov test has a function class of indicator functions, [math]\displaystyle{ \mathcal F = \{ 1_{(-\infty, t]} : t \in \mathbb R \} }[/math].
  • The kernel maximum mean discrepancy (MMD) has [math]\displaystyle{ \mathcal F }[/math] the unit ball in a reproducing kernel Hilbert space. This distance is particularly easy to estimate from samples, requiring no optimization; it is a proper metric exactly when the underlying kernel is characteristic.[6]
  • The energy distance, as a special case of the maximum mean discrepancy,[7] is generated by the unit ball in a particular reproducing kernel Hilbert space.
  • Defining [math]\displaystyle{ \mathcal F }[/math] by functions with a bounded Sobolev norm gives a useful distance for generative modeling, among other applications.[8]
  • Functions with bounded Besov norm generalize many other forms of IPM and are amenable to theoretical analysis.[9][10]
  • Many variants of generative adversarial networks and classifer-based two-sample tests[11][12] use a "neural net distance"[13][14] where [math]\displaystyle{ \mathcal F }[/math] is a class of neural networks; these are not metrics for typical fixed-size networks, but could be for other classifiers. For Wasserstein GANs in particular, it has been argued that analysis in terms of this distance and not the Wasserstein they approximate is very important to the behavior of these models.[13][15][16]

Relationship to f-divergences

The f-divergences are probably the best-known way to measure dissimilarity of probability distributions. It has been shown[5] that the only functions which are both IPMs and f-divergences are of the form [math]\displaystyle{ c \, \operatorname{TV}(P, Q) }[/math], where [math]\displaystyle{ c \in [0, \infty] }[/math] and [math]\displaystyle{ \operatorname{TV} }[/math] is the total variation distance between distributions.

One major difference between f-divergences and most IPMs is that when P and Q have disjoint support, all f-divergences take on a constant value;[17] by contrast, IPMs where functions in [math]\displaystyle{ \mathcal F }[/math] are "smooth" can give "partial credit." For instance, consider the sequence [math]\displaystyle{ \delta_{1/n} }[/math] of Dirac measures at 1/n; this sequence converges in distribution to [math]\displaystyle{ \delta_0 }[/math], and many IPMs satisfy [math]\displaystyle{ D_{\mathcal F}(\delta_{1/n}, \delta_0) \to 0 }[/math], but no nonzero f-divergence can satisfy this. That is, many IPMs are continuous in weaker topologies than f-divergences. This property is sometimes of substantial importance,[18] although other options also exist, such as considering f-divergences between distributions convolved with continuous noise.[18][19]

Estimation from samples

Because IPM values between discrete distributions are often sensible, it is often reasonable to estimate [math]\displaystyle{ D_{\mathcal F}(P, Q) }[/math] using a simple "plug-in" estimator: [math]\displaystyle{ D_{\mathcal F}(\hat P, \hat Q) }[/math] where [math]\displaystyle{ \hat P }[/math] and [math]\displaystyle{ \hat Q }[/math] are empirical measures of sample sets. These empirical distances can be computed exactly for some classes [math]\displaystyle{ \mathcal F }[/math];[5] estimation quality varies depending on the distance, but can be minimax-optimal in certain settings.[14][20][21]

When exact maximization is not available or too expensive, another commonly used scheme is to divide the samples into "training" sets (with empirical measures [math]\displaystyle{ \hat P_\mathit{train} }[/math] and [math]\displaystyle{ \hat Q_\mathit{train} }[/math]) and "test" sets ([math]\displaystyle{ \hat P_\mathit{test} }[/math] and [math]\displaystyle{ \hat Q_\mathit{test} }[/math]), find [math]\displaystyle{ \hat f }[/math] approximately maximizing [math]\displaystyle{ \big| \hat P_\mathit{train} f - \hat Q_\mathit{train} f \big| }[/math], then use [math]\displaystyle{ \big| \hat P_\mathit{test} \hat f - \hat Q_\mathit{test} \hat f \big| }[/math] as an estimate.[22][12][23][24] This estimator can possibly be consistent, but has a negative bias[22]. In fact, no unbiased estimator can exist for any IPM[22], although there is for instance an unbiased estimator of the squared maximum mean discrepancy.[4]

References

  1. ↑ 1.0 1.1 1.2 Müller, Alfred (June 1997). "Integral Probability Metrics and Their Generating Classes of Functions". Advances in Applied Probability 29 (2): 429–443. doi:10.2307/1428011. 
  2. ↑ Zolotarev, V. M. (January 1984). "Probability Metrics". Theory of Probability & Its Applications 28 (2): 278–302. doi:10.1137/1128025. 
  3. ↑ Arjovsky, Martin; Chintala, Soumith; Bottou, Léon (2017-07-17). "Wasserstein Generative Adversarial Networks" (in en). International Conference on Machine Learning (PMLR): 214–223. https://proceedings.mlr.press/v70/arjovsky17a.html. 
  4. ↑ 4.0 4.1 Gretton, Arthur; Borgwardt, Karsten M.; Rasche, Malte J.; Schölkopf, Bernhard; Smola, Alexander (2012). "A Kernel Two-Sample Test". Journal of Machine Learning Research 13: 723–773. https://jmlr.org/papers/volume13/gretton12a/gretton12a.pdf. 
  5. ↑ 5.0 5.1 5.2 Sriperumbudur, Bharath K.; Fukumizu, Kenji; Gretton, Arthur; Schölkopf, Bernhard; Lanckriet, Gert R. G. (2009). "On integral probability metrics, φ-divergences and binary classification". arXiv:0901.2698 [cs.IT].
  6. ↑ Fukumizu, Kenji; Gretton, Arthur; Sun, Xiaohui; Schölkopf, Bernhard (2007). "Kernel Measures of Conditional Dependence". Advances in Neural Information Processing Systems. https://papers.nips.cc/paper_files/paper/2007/hash/3a0772443a0739141292a5429b952fe6-Abstract.html. 
  7. ↑ Sejdinovic, Dino; Sriperumbudur, Bharath; Gretton, Arthur; Fukumizu, Kenji (2013). "Equivalence of distance-based and RKHS-based statistics in hypothesis testing". The Annals of Statistics 41 (5): 2263–2291. doi:10.1214/13-aos1140. 
  8. ↑ Mroueh, Youssef; Li, Chun-Liang; Sercu, Tom; Raj, Anant; Cheng, Yu (2018). "Sobolev GAN". International Conference on Learning Representations. https://openreview.net/forum?id=SJA7xfb0b. 
  9. ↑ Uppal, Ananya; Singh, Shashank; Póczos, Barnabás (2019). "Nonparametric Density Estimation & Convergence Rates for GANs under Besov IPM Losses". Advances in Neural Information Processing Systems. https://papers.nips.cc/paper_files/paper/2019/hash/fb09f481d40c4d3c0861a46bd2dc52c0-Abstract.html. 
  10. ↑ Uppal, Ananya; Singh, Shashank; Póczos, Barnabás (2020). "Robust Density Estimation under Besov IPM Losses". Advances in Neural Information Processing Systems. https://papers.nips.cc/paper_files/paper/2020/hash/39d4b545fb02556829aab1db805021c3-Abstract.html. 
  11. ↑ Kim, Ilmun; Ramdas, Aaditya; Singh, Aarti; Wasserman, Larry (February 2021). "Classification accuracy as a proxy for two-sample testing". The Annals of Statistics 49 (1). doi:10.1214/20-AOS1962. 
  12. ↑ 12.0 12.1 Lopez-Paz, David; Oquab, Maxime (2017). "Revisiting Classifier Two-Sample Tests". International Conference on Learning Representations. https://openreview.net/forum?id=SJkXfE5xx. 
  13. ↑ 13.0 13.1 Arora, Sanjeev; Ge, Rong; Liang, Yingyu; Ma, Tengyu; Zhang, Yi (2017). "Generalization and Equilibrium in Generative Adversarial Nets (GANs)". International Conference on Machine Learning. 
  14. ↑ 14.0 14.1 Ji, Kaiyi; Liang, Yingbin (2018). "Minimax Estimation of Neural Net Distance". Advances in Neural Information Processing Systems. 
  15. ↑ Stanczuk, Jan; Etmann, Christian; Lisa Maria Kreusser; Schönlieb, Carola-Bibiane (2021). "Wasserstein GANs Work Because They Fail (To Approximate the Wasserstein Distance)". arXiv:2103.01678 [stat.ML].
  16. ↑ Mallasto, Anton; Montúfar, Guido; Gerolin, Augusto (2019). "How Well do WGANs Estimate the Wasserstein Metric?". arXiv:1910.03875 [cs.LG].
  17. ↑ Sutherland, Danica J.. "Computing Jensen-Shannon Divergence between discrete and continuous distribution". Stack Exchange Network. https://stats.stackexchange.com/a/621718. Retrieved 18 July 2023. 
  18. ↑ 18.0 18.1 Arjovsky, Martin; Bettou, Léon (2017). "Towards Principled Methods for Training Generative Adversarial Networks". International Conference on Learning Representations. 
  19. ↑ Sønderby, Casper Kaae; Caballero, Jose; Theis, Lucas; Shi, Wenzhe; Huszár, Ferenc (2017). "Amortised MAP Inference for Image Super-resolution". International Conference on Learning Representations: Appendix C. 
  20. ↑ Tolstikhin, Ilya O.; Sriperumbudur, Bharath K.; Schölkopf, Bernhard (2016). "Minimax Estimation of Maximum Mean Discrepancy with Radial Kernels". Advances in Neural Information Processing Systems. https://papers.nips.cc/paper_files/paper/2016/hash/5055cbf43fac3f7e2336b27310f0b9ef-Abstract.html. 
  21. ↑ Singh, Shashank; Póczos, Barnabás (2018). "Minimax Distribution Estimation in Wasserstein Distance". arXiv:1802.08855 [math.ST].
  22. ↑ 22.0 22.1 22.2 Bińkowski, Mikołaj; Sutherland, Danica J.; Arbel, Michael; Gretton, Arthur (2018). "Demystifying MMD GANs". International Conference on Learning Representations. https://openreview.net/forum?id=r1lUOzWCW. 
  23. ↑ Liu, Feng; Xu, Wenkai; Lu, Jie; Zhang, Guangquan; Gretton, Arthur; Sutherland, Danica J. (2020). "Learning Deep Kernels for Non-Parametric Two-Sample Tests". International Conference on Machine Learning. https://proceedings.mlr.press/v119/liu20m.html. 
  24. ↑ Kübler, Jonas M.; Jitkrittum, Wittawat; Schölkopf, Bernhard; Muandent, Krikamol (2021). "A Witness Two-Sample Test". International Conference on Artificial Intelligence and Statistics. https://proceedings.mlr.press/v151/kubler22a.html. 



Retrieved from "https://handwiki.org/wiki/index.php?title=Integral_probability_metric&oldid=3386149"